package com.atguigu.structures;

public class CustomerQuickSortExample {
    public static void main(String[] args) {
        int[] array = {2, 8, 7, 1, 3, 5, 4, 6};
        quickSort(array, 0, 7);
        for (int j : array) {
            System.out.println(j);
        }
    }


    public static void quickSort(int[] arr, int start, int end) {
        if (start<end){
            int p = partition(arr, start, end);
            quickSort(arr, start, p - 1);
            quickSort(arr, p + 1, end);
        }
    }

    /**
     * f=最后一个值
     * 循环过程中：
     * l永远指向比f小的前一个
     * r永远指向比f大的后一个
     * 当r遇到比f小的值时l+1  l与r交换元素位置
     * <p>
     * 循环结束后最终交换end与l+1的位置
     */
    public static int partition(int[] arr, int start, int end) {
        int f = arr[end];
        int l = start - 1;
        for (int r = start; r < end; r++) {
            if (arr[r] < f) {
                l += 1;
                swap(arr, l, r);
            }
        }
        swap(arr, l + 1, end);
        return l + 1;
    }

    public static void swap(int[] arr, int a, int b) {
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }
}
